#include <stdio.h>
#include <malloc.h>
#include <math.h>
#include"..\Stack\zyf_Stack.h"
#define MAX_SIZE 100
#define NULLKEY '?'
#define MAX_NODE 50
#define OK 1
#define ERROR 2
typedef int ElmeType;
typedef int Status;


/*
	对于完全二叉树编号,编号为i存在一维数组i-1位置

	对于一般的二叉树,将其每个结点与完全二叉树的结点对照,存储在一维数组中
	实现方案,先扩展成完全二叉树大小,按照序号对应存
	最坏的情况下,深度为k的二叉树,需要2^k - 1  个存储空间
*/

//typedef telemtype sqbitree[MAX_SIZE];

/*
	二叉链表结点.有三个域,一个数据域,两个分别指向左右子结点的指针域
	二叉树含有n个结点,则它的二叉链表中必有2n个指针域,其中必有n+1个空的链域(叶子结点有两个空域,度为1的一个空域)
	分支数(不为空的指针域)为n-1,2n-(n-1) = n+1
*/
typedef struct btNode2
{
	ElmeType data;
	struct BTNode *Lchild, *Rchild;
}BTNode2,*BiTree2;

/*
	三叉链表.除二叉链表三个域外,再增加一个指针域,用来指向结点的父节点.
*/

typedef struct btnode3
{
	ElmeType data;
	struct BTNode3 *Lchild,*Rchild,*parent;
}BTNode3,*BiTree3;

/*
	二叉树的遍历：
	D为根,L为左,R为右,一共有六种方案
	DLR,LDR,LRD,DRL,RDL,RLD
	若规定先左后右则只有:DLR,LDR,LRD
	DLR-先序遍历
		第一个是根结点
	LDR-中序遍历
		找到中间某个位置根结点.左边为左子树右边为右子树
	LRD-后序遍历
		最后一个是根结点

	任何结点过了三遍
*/

/*
	二叉树的建立:
	按满二叉树的方式建立
	对每个结点i为编号,从小到大
	ch:结点的内容,假设是字符
	借助一个一维数组S[n],编号i的结点保存在S[i]中
*/
BTNode2 *CreateBTree2_1(void)
{
	BTNode2 *T,*p,*s[MAX_SIZE];
	char ch;
	int i,j;
	while (1)
	{
		scanf("%d",&i);
		if (i == 0)
			break;
		else
		{
			ch = getchar();
			p = (BTNode2 *)malloc(sizeof(BTNode2));
			P -> data = ch;
			p -> Lchild = p -> Rchild = NULL;
			s[i] = p;

			if (i == 1)
				T = p;
			else
			{
				j = i/2; /*j是i的双亲结点编号*/
				if (i%2 == 0)
					s[j] -> Lchild = p;
				else
					s[j] -> Rchild = p;
			}
		}
	}

	return T;
}

/*
	二叉树的建立:
	按先序遍历的方式建立
	对一颗二叉树进行扩充,就可以得到该二叉树所扩充的二叉树
	若是扩充结点:令根指针为null
	若是正常结点:动态地为根指针分配一个结点,将该值赋给根结点
		然后递归的创建根的左子树和右子树
	char类型扩充结点值为 '？'
	int类型扩充结点值为0或者-1
*/
BTNode2 *CreateBTree2_2(BTNode2 *T)
{
	char ch;
	ch = getchar();
	if (ch == NULLKEY)
	{
		T = NULL;
		return T;
	}
	else
	{
		T = (BTNode2 *)malloc(sizeof(BTNode2));
		T -> data = ch;
		CreateBTree2_2(T -> Lchild);
		CreateBTree2_2(T -> Rchild);

		return T;
	}

}

/*
	visit为对栈进行操作的函数,这里用打印

	Status (* Visit)(ElemType e)
	这是定义了一个函数指针，函数指针名是visit。它规定指向的函数的参数必须是ElemType类型，返回值必须是Status。
	如你定义了一个函数：
	Status fun(ElemType e)
	{
	}
	则可以这样使用：
	visit = &fun； //取函数地址
	然后直接通过指针调用该函数：
	Status s = visit(e);
*/
Status visit(int e)
{
	printf("该结点的值为：%d",e);
}
/*
	先序遍历二叉树
	递归算法
	若二叉树为空,则遍历结束;
	否则,
	1.访问根结点;
	2.先序遍历左子树;
	3.先序遍历右子树;

	非递归算法的先序遍历
	设T是指向二叉树根结点的指针变量
	若二叉树为空,则返回;
	否则,令p=T;
	1.访问p所指向的结点;
	2.q = p->Rchild,若q不为空,则q进栈;
	3.p = p-> Lchild,若p不为空,转(1),否则转到(4);
	4.退栈到p,转(1),直到栈空为止
*/


//递归算法的先序遍历
void PreorderTraverse1(BTNode2 *T)
{
	if (T!=NULL)
	{
		visit(T -> data);
		PreorderTraverse1(T -> Lchild);
		PreorderTraverse1(T -> Rchild);
	}
}

//非递归算法的先序遍历
void PreorderTraverse2(BTNode2 *T)
{	/*
		stack是一个存放树结点地址的数组,
		因为栈的本质就是线性表不让它进行一些操作,所以
		设置一个数组只让它在数组尾部模拟进栈出栈即可,
		不用专门引入栈的结构体增加代码难度
		top为栈顶指针
	*/
	BTNode2 *stack[MAX_NODE],*p = T,*q;
	int top = 0;
	if (T == NULL)
		printf("Binary Tree is empty!\n");
	else
	{
		do
		{
			visit(p -> data);
			q = p -> Rchild;
			if (q != NULL)
				stack[++top] = q;
			p = p -> Lchild;
			if (p == NULL)
			{
				P = stack[top];
				top--;
			}
		} while (p! = NULL);//注意循环条件

	}
}

/*
	中序遍历:
	递归算法
	若二叉树为空,则遍历结束;
	否则:
	1.中序遍历左子树(即递归调用本算法);
	2.访问根结点(visit);
	3.中序遍历右子树.

	非递归算法
	设T是指向二叉树根结点的指针变量
	若二叉树为空,则返回;
	否则,令p=T
	1.若p不为空,p进栈,p = p -> Lchild;
	2.否则(p为空),退栈到p,访问p所指向的结点
	3.p = p -> Rchild ,转(1)
	直到栈空
*/

//递归算法的中序遍历
void InoderTraverse1(BTNode2 *T)
{
	if (T != NULL)
	{
		InoderTraverse1(T -> Lchild);
		visit(T ->data);
		InoderTraverse1(T -> Rchild);
	}
}

//非递归算法的中序遍历
/*
	先直接抡,把最左边的左孩子全都抡进栈里,
	遇到空在退出循环,判断栈是否为空,为空bool标识赋值为0
	在出栈打印一个,在把这个出栈回退的结点的右结点的子树
	按上述重复抡,一直到栈空了,推出循环

	有两个循环,一个抡左孩子,一个判断bool值
*/
void InoderTraverse2_1(BTNode2 *T)
{
	BTNode2 *stack[MAX_NODE],*p = T;
	int top = 0,bool = 1;
	if (T == NULL)
		printf("Binary Tree is empty!\n");
	else
	{
		do
		{
			/*
			if (p != NULL)
			{
				stack[++top] = p;
				p = p -> Lchild;
				if (p == NULL)
					p = stack[top];
					visit(p -> data);
					p = p -> Rchild;
			}
			*/
			while (p != NULL)
			{
				stack[++top] = p;
				p = p -> Lchild;
			}

			if (top == 0)
				bool = 0;
			else
			{
				p = stack[top--];
				visit(p -> data);
				p = p -> Rchild;
			}

		}while (bool!=0);
	}


}

/*
Status InoderTraverse2_2(BTNode2 *T, Status (*visit)(ElemType e))
{
	SqStack S;
	BTNode2 *p;
	Init_Stack(&S);
	p = T;
	while (p || !EmptyStack(S))
	{
		if (p)
		{
			push(&S,p);
			p = p -> Lchild;
		}
		else
		{
			pop(S,&p);
			if (ERROR == visit(p -> data)) return ERROR;
			p = p -> Rchild;
		}
	}
}
*/

/*
	后序遍历
	递归算法
	若二叉树为空,则遍历结束;
	否则.
	1.后序遍历左子树(递归调用本算法)
	2.后序遍历右子树(递归调用本算法)
	3.访问根结点

	非递归算法
	根结点被最后访问.
	因此,在遍历过程中,当搜索指针指向某一根结点时,不能立即访问,
	而要在先遍历其左子树,此时根结点进栈
	当其左子树遍历完后,搜索到根结点时,还是不能访问,还需要遍历其右子树
	此时根结点还需再次进栈,当其右子树遍历完后到该根结点时,才能被访问

	因此,设立一个状态标志变量tag
	tag 0 结点暂不能访问
	tag 1 结点可以访问
	其次,设立两个堆栈S1,S2, S1保存结点,S2保存状态标志tag
	S1,S2共用一个栈顶指针

	若二叉树为空,则返回;
	否则,p = T
	1.第一次经过p,不访问
	  p进S1,tag赋值为0,进栈S2,p = p -> Lchild
	2.若p不为空,重复(1),否则,取状态标志值
	3.若tag = 0：对栈S1,不访问,不出栈;
	  修改S2栈顶元素值(tag赋值1),
	  取S1栈顶元素的右子树,即p = S1[top] -> Rchild，转到(1)
	4.若tag = 1：S1退栈,访问该结点
	直到栈空
*/

//递归算法的后序遍历
void PostorderTraverse1(btNode2 *T)
{
	if (T! = NULL)
	{
		PostorderTraverse1(T -> Lchild);
		PostorderTraverse1(T -> Rchild);
		visit(T -> data);
	}
}

//非递归算法的后序遍历
Status PostorderTraverse2_1(BTNode2 *T)
{
	BTNode2 *S1[MAX_NODE],*p = T;
	int S2[MAX_NODE],top = 0,bool = 1;//bool判断栈是否为空

	if (T == NULL)
	{
		printf("tree is empty\n");
		return ERROR;
	}
	else
	{
		do
		{
			while (p! =NULL)
			{
				S1[++top] = p;
				S2[top] = 0;
				p = p -> Lchild;
			}

			if (top == 0)
				bool = 0;
			else if (S2[top] == 0)
			{
				p = S1[top] -> Rchild;
				S2[top] = 1;
			}
			else
			{
				p = S1[top];
				top--;
				visit(p -> data);
				p = NULL;
			}
		} while(bool! = 0);
	}
/*		
typedef struct 
{
	BTNode2 *ptr;//结点指针
	enum tag{L,R};//该结点的退栈标签
	//L表示从左子树退出,访问右子树
	//R表示从右子树推出,访问根
}StackNode;

//第二种非递归后续遍历
void PostorderTraverse2_2(BTNode2 *T)
{
	stack S;
	Init_Stack(S);
	StackNode w;
	BTNode2 *p = T;

	do
	{
		while (p != NULL)
		{
			w.ptr = p;
			w.tag = L;
			push(S,w);
			p = p -> Lchild;
		}

		int succ = 1;

		while (succ && !EmptyStack(S))
		{
			pop(S,w);
			p = w.ptr;
			switch (w.tag)
			{
				case L: w.tag = R; push(S.w);
						succ = 0;
						p = p -> Rchild;
						break;
				case R: visit(p -> data);
			}
		}

	}while (!EmptyStack(S));

}
*/

//层次遍历
/*
	从根结点开始遍历,自上而下,从左至右,访问树中的各结点
	设置一个队列,初始化时为空
	设T是指向根结点的指针变量,层次遍历非递归算法是:
	若二叉树为空,则返回;
	否则,令p=T,入队;
	1.队首元素出队到p
	2.访问p所指向的结点
	3.将p所指向的结点的左右子结点一词入队.直至队空为止.
*/

void LeveloderTraverse(BTNode2 *T)
{
	BTNode2 *Queue[MAX_NODE],*p = T;
	int front = 0,rear = 0;

	if (p != NULL)
	{
		Queue[++rear] = p;//根结点入队
		//队列暂时使用顺序队列
		while (front < rear)
		{
			p = Queue[++front];
			visit(p -> data);

			if (p -> Lchild != NULL)
				Queue[++rear] = p -> Lchild;
			if (p -> Rchild != NULL)
				Queue[++rear] = p -> Rchild;
		}
	}
}


//求二叉树的叶子结点数,非递归遍历的先序遍历
int CountLeaf1(BTNode2 *T)
{
	BTNode2 *Stack[MAX_NODE], *p = T;
	int top = 0; num = 0;

	if (T != NULL)
	{
		Stack[++top] = p;
		while (top > 0)
		{
			p = Stack[top--];

			if (p -> Lchild == NULL && p -> Rchild == NULL)
				num++;
			if (p ->Rchild != NULL)
				Stack[++top] = p -> Rchild;
			if (p -> Lchild != NULL)
				Stack[++top] = p -> Lchild;
		}

		return num;
	}
}

//求二叉树的叶子结点数,递归的先序遍历来计算
void CountLeaf2(BTNode2 *T,int *num)
{
	if (T != NULL)
	{
		if (p -> Lchild == NULL && p -> Rchild == NULL)
			(*num)++;

		CountLeaf2(T -> Lchild,num);
		CountLeaf2(T -> Lchild,num);
	}
}

//求二叉树的深度
int search_depth(BTNode2 *T)
{
	BTNode2 *Queue[MAX_NODE],*p = T;
	int front = 0, rear = 0, depth = 0; level;
	//level总是指向访问层的最后一个结点在队列的位置

	if (T != NULL)
	{
		Queue[++rear] = p;
		level = rear; /*根是第一层的最后一个结点*/

		while (front < rear)
		{
			p = Queue[++front];

			if (p -> Lchild != NULL)
				Queue[++rear] = p -> Lchild;
			if (p -> Rchild != NULL)
				Queue[++rear] = p -> Rchild;

			if (front == level)
			{/*访问的是当前层的最后一个结点*/	
				depth++;
				level = rear;
			}
		}
	}
}

/*
	判断二叉树是否为完全二叉树(即顺序二叉树)
	完全二叉树特点：没有左子树是空的而右子树不为空单独存在的
	技巧：按层次遍历遍历,先把所有结点(不管是当前结点是否有左
	右孩子)都入队列.若为完全二叉树,则层次遍历是得到的肯定是
	一个连续的不包含指针的序列.如果序列中出现了空指针,则说明
	不是完全二叉树.
*/

Status judgeComplete1(BTNode2 *T)
{//基于层次遍历
	int tag = 0,front = 0,rear = 0;
	BTNode2 *p = T,*Queue[MAX_NODE];

	if (T == NULL)
		return ERROR;
	else
	{
		Queue[++rear] = p;
	

	while (front < rear)
	{
		p = Queue[++front];

		if (p -> Lchild != NULL && tag != 0)
			Queue[++rear] = p -> Lchild;
		else if (p -> Lchild != NULL)
			return ERROR;
		else
			tag = 1;
		/*
			遇到一个为空tag置为1,如果下一个结点不为空,
			则不是完全二叉树,下一个结点依旧是空并且直到
			结点,依旧是完全二叉树
		*/

		if (p -> Rchild != NULL && tag != 0)
			Queue[++rear] = p -> Rchild;
		else if (p -> Rchild != NULL)
			return ERROR;
		else
			tag = 1;
	}

	}
	return OK;
}

//判断是否为完全二叉树
Status judgeComplete2(BTNode2 *T)
{
	int tag = 0,front = 0,rear = 0;
	BTNode2 *p = T,*Queue[MAX_NODE];

	if (p == NULL)
		return ERROR;
	else
	{
		Queue[++rear] = p;
	

	while (front < rear)
	{
		p = Queue[++front];

		if(p != NULL)
		{
			if (tag != 0)
				return ERROR;

			Queue[++rear] = p -> Lchild;
			Queue[++rear] = p -> Rchild;
		}
		else
			tag = 1;
	}

	}

	return OK;
}

/*
	用二叉树遍历的思想判断一棵二叉树是否是平衡二叉树
*/

void JudgeBLTree(BTNode2 *T,int *balance, int *height)
{
	int b_l,b_r,h_l,h_r;

	if (T == NULL)
	{
		*balance = 1;
		*height = 0;
	}
	else if (T -> Lchild == NULL && T -> Rchild == NULL)
	{
		*balance = 1;
		*height = 1;
	}
	else
	{
		JudgeBLTree(T -> Lchild,&b_l,&h_l);
		JudgeBLTree(T -> Rchild,&b_r,&h_r);

		*height = 1 + ((h_l > h_r)?h_l:h_r);

		if ((int)abs(*height) < 2)
		{
			*balance = b_l & b_r;
		}
		else
			*balance = 0;
	}
}